<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /**
             *
             *
             */
            class Node {
                constructor(value) {
                    this.key = value;
                    this.left = null;
                    this.right = null;
                }
            }

            class TreeStructure {
                constructor() {
                    this.root = null;
                }
                insertNode(key) {
                    //插入节点
                    let newNode = new Node(key);
                    //判断是不是第一次添加
                    if (this.root === null) {
                        //如果是空的话就添加
                        this.root = newNode;
                    } else {
                        //存在时，就调用插入的函数
                        this.insertChildNode(this.root, newNode);
                    }
                }
                //插入子节点，参数就是二叉树下的节点
                insertChildNode(node, newNode) {
                    //判断是不是左右节点
                    if (node.key > newNode.key) {
                        //判断左边节点是否有值
                        if (node.left === null) {
                            node.left = newNode;
                        } else {
                            //有值的话调用函数本身，循环
                            this.insertChildNode(node.left, newNode);
                        }
                    } else {
                        //判断边节右边点是否有值
                        if (node.right === null) {
                            node.right = newNode;
                        } else {
                            //有值的话调用函数本身，循环
                            this.insertChildNode(node.right, newNode);
                        }
                    }
                }
                //判断最小节点
                minNode(key = this.root) {
                    //判断key是否为空
                    if (key === null) {
                        //如果是的话直接返回underginde
                        return undefined;
                    } else {
                        //如果不是的话就给节点写一个key的值
                        //定义一个key初始值
                        let current = key;
                        //子节点和左节点不为空的情况下
                        while (current !== null && current.left !== null) {
                            current = current.left;
                        }
                        //返回一个 current
                        return current;
                    }
                }
                //判断最大节点
                maxNode(key = this.root) {
                    if (key === null) {
                        //判断当前树是否为空树，
                        return undefined; //如果是的话就返回undefined
                    } else {
                        //定义key的初始值
                        let current = key;
                        //取右节点的最大值
                        while (current !== null && current.right !== null) {
                            current = current.right;
                        }
                        //返回一个current
                        return current;
                    }
                }
                //通过一个key值查找这个节点
                searchNode(key) {
                    //输入根和左或者右边子节点
                    return this.search(this.root, key);
                }
                //查找
                search(node, key) {
                    //判断node这个节点是否存在
                    if (node === null) {
                        //如果空的话则返false
                        return false;
                    }
                    //当这个节点存在时,判断是向左还是向右查找
                    if (node.key > key) {
                        return this.search(node.left, key);
                    } else if (node.key < key) {
                        return this.search(node.right, key);
                    } else {
                        return true;
                    }
                }
                removeNode(key) {
                    this.root = this.remove(this.root, key);
                }
                //删除一个节点
                remove(node, key) {
                    //判断节点是否存在
                    if (node === null) {
                        //返回一个空
                        return null;
                    }
                    //判断   值最小就左边删除
                    if (node.key > key) {
                        //如果节点的值大于输入的值 删除node的左子节点
                        node.left = this.remove(node.left, key);
                        //
                        return node;
                        // 值大的时候就去右边删除;
                    } else if (node.key < key) {
                        //node key <key输出的值
                        //删除node的右子节点
                        node.right = this.remove(node.right, key);
                        return node;
                    } else {
                        if (node.left === null && node.right === null) {
                            node = null;
                            return node;
                        }
                        if (node.left === null) {
                            node = node.right;
                            return node;
                        } else if (node.right === null) {
                            node = node.left;
                            return node;
                        }
                        //最后的操作
                        let minNode = this.minNode(node.right);
                        node.key = minNode.key;
                        node.right = this.remove(node.right, minNode.key);
                        return node;
                    }
                }
                middleOrder() {
                    this.mOrder(this.root);
                }
                //二叉树的中序遍历,
                //先执行左边的节点,返回上一层后在执行右边的节点
                mOrder(node) {
                    if (node !== null) {
                        this.mOrder(node.left);
                        console.log(node);
                        this.mOrder(node.right);
                    }
                }
                //上一个中间节点
                prevOrder() {
                    this.pOrder(this.root);
                }
                //二叉树的前序遍历,
                //先执行根节点,然后进行左边节点的遍历，在进行右边节点的遍历
                pOrder(node) {
                    //如果输入节点不为空  则找到左节点的上一个中间节点
                    if (node !== null) {
                        console.log(node);
                        this.pOrder(node.left);
                        this.pOrder(node.right);
                    }
                }
                //下一个中间节点
                nextOrder() {
                    this.nOrder(this.root);
                }
                //二叉树后序遍历
                //先执行左边后再执行右边，如此左右左右最后打印根节点
                nOrder(node) {
                    if (node !== null) {
                        this.nOrder(node.left);
                        this.nOrder(node.right);
                        console.log(node);
                    }
                }
                height() {
                    //返回他的一个高度
                    return this.getHeight(this.root);
                }
                //设置一个队列,首先将根节点入队列,然后依次行队列中退出一个元素
                getHeight(node) {
                    //如果节点为空的返回0
                    if (node === null) return 0;
                    //一层
                    let height = 1;
                    let newNode;
                    //定义一个数组存放左右节点
                    let arr = [node, null];
                    //如果不对就不执行
                    while ((newNode = arr.shift()) !== undefined) {
                        if (newNode === null) {
                            if (!arr.length) return height;
                            height++;
                            arr.push(null);
                            continue;
                        }
                        newNode.left && arr.push(newNode.left);
                        newNode.right && arr.push(newNode.right);
                        console.log(arr, "arr");
                    }

                    return height;
                }
            }

            let t = new TreeStructure();
            t.insertNode(11);
            t.insertNode(7);
            t.insertNode(15);
            t.insertNode(5);
            t.insertNode(9);
            t.insertNode(13);
            t.insertNode(20);
            t.insertNode(18);
            t.insertNode(25);
            t.insertNode(30);

            console.log("t", t.prevOrder());

            ///aaaabbbbccccccc、
            /**
             * 先序遍历· 根·左·右
             * 使用迭代的方法，首先的话就是判断根节点是否为空,为空的话就返回空数组
             * 然后在定义俩个数组，res数组存放先序的排列，stack数组是暂存接点的
             */
            const a = (root) => {
                //判断根节点是否为空  为空的话返回空数组
                if (!root) return [];
                //定义俩个空数组，res先序的排序 ··stack暂存节点
                let stack = [],
                    res = [];
                while (root) {
                    //添加  根·左·右 节点
                    res.push(root.val);
                    if (root.right) stack.push(root.right);
                    if (root.left) stack.push(root.left);
                    root = stack.pop();
                }
                return root;
            };
            /**
             * 中序遍历·左·跟·右
             * 节点开始,you左节点，就将父节点先入stack栈，知道叶子结点，将叶子结点入res栈
             * 找其结点是否存在，不存在则回溯，继续出栈，存在的话，则将右节点当做新的根节点
             * 重复开始的过程，直到stack为空，输出res栈
             */
            const b = (root) => {
                let stack = [],
                    res = [];
                while (root) {
                    if (!root.left && !root.right) {
                        res.push(root.val);
                        root = stack.pop();
                        root && (root.left = null); //每次出栈后要判断root是否为空,空则循环结束
                    } else if (root.left) {
                        stack.push(root);
                        root = root.left;
                    } else if (root.right) {
                        res.push(root.val);
                        root = root.right;
                    }
                }
                return res;
            };
            /**
             * 左、右、后
             * 根、右、左 = 后序
             */
            const c = (root) => {
                let stack = [],
                    res = [];
                while (root) {
                    if (root.left) {
                        //当前二叉树的最左节点
                        stack.push(root);
                        //访问当前节点的左孩子
                        root = root.left;
                    } else if (root.right) {
                        stack.push(root);
                        //访问当前节点的右孩子
                        root = root.right;
                    } else {
                        res.push(root.val);
                        root = stack.pop();
                        //右后进，右先出， 根右左
                        if (root && root.left) {
                            root.left = null;
                        } else if (root && root.right) {
                            root.right = null;
                        }
                    }
                }
                return res;
            };
        </script>
    </body>
</html>
